﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
    class P0040 : IProblem
    {
        public void Run()
        {
            var s = new Solution();
            s.CombinationSum2(new int[] { 2,5,2,1,2 }, 5);
        }

        public class Solution
        {
            private HashSet<int> m_set = new HashSet<int>();
            public IList<IList<int>> CombinationSum2(int[] candidates, int target)
            {
                var path = new List<int>();
                var pathList = new List<IList<int>>();

                var list = new List<int>(candidates);
                list.Sort();
                candidates = list.ToArray();

                Backtrack(candidates, 0, target, path, pathList);


                return pathList;
            }

            public void Backtrack(int[] candidates, int index, int target, IList<int> path, IList<IList<int>> res)
            {
                var i = index;
                if (i >= candidates.Length)
                    return;

                var candidate = candidates[i];

                //刚好等于
                if (candidate == target)
                {
                    path.Add(candidate);
                    res.Add(new List<int>(path));
                    path.RemoveAt(path.Count - 1);
                    return;
                }
                //候选小于目标 如 2 < 7; 则需要继续向下决策
                if (candidate < target)
                {
                    //拿 
                    path.Add(candidate);
                    Backtrack(candidates, i + 1, target - candidate, path, res);
                    path.RemoveAt(path.Count - 1);

                    //不拿
                    bool hasRepeat = false; ;
                    while (i < candidates.Length - 1)
                    {
                        if (candidates[i + 1] != candidate)
                        {
                            break;
                        }
                        hasRepeat = true;
                        i++;
                    }
                    if (!m_set.Contains(candidate))
                    {
                        if (hasRepeat)
                            m_set.Add(candidate);
                        Backtrack(candidates, i + 1, target, path, res);
                    }


                }
                //候选大于目标 则结束决策,向上回溯
                if (candidate > target)
                {

                }
                //结束时向上回溯
            }
        }
    }
}
